//
//  BinaryTreeNode.m
//  BinaryTree
//
//  Created by DeLong Yang on 2017/7/27.
//  Copyright © 2017年 DeLong Yang. All rights reserved.
/*
    递归思想 贯穿于 tree的始终
    我们一般 按照 从左到右 从上到下的顺序
 */

#import "BinaryTreeNode.h"
#import "TreeNodeProperty.h"   //   node property

@implementation BinaryTreeNode


/**
 *  创建二叉排序树
 *  二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值
 *
 *  @param values 数组
 *
 *  @return 二叉树根节点
 */
+ (BinaryTreeNode *)createTreeWithValues:(NSArray *)values {
    
    BinaryTreeNode *root = nil;
    for (NSInteger i=0; i<values.count; i++) {
        NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
        root = [BinaryTreeNode addTreeNode:root value:value];
    }
    return root;
}

/**
 *  向二叉排序树节点添加一个节点
 *
 *  @param treeNode 根节点
 *  @param value    值
 *
 *  @return 根节点
 */
+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {
    //根节点不存在，创建节点
    if (!treeNode) {
        treeNode = [BinaryTreeNode new];
        treeNode.value = value;
        NSLog(@"node:%@", @(value));
    }
    else if (value <= treeNode.value) {
        NSLog(@"to left");
        //值小于根节点，则插入到左子树
        treeNode.leftNode = [BinaryTreeNode addTreeNode:treeNode.leftNode value:value];
    }
    else {
        NSLog(@"to right");
        //值大于根节点，则插入到右子树
        treeNode.rightNode = [BinaryTreeNode addTreeNode:treeNode.rightNode value:value];
    }
    
    return treeNode;
}

/**
 *  二叉树中某个位置的节点（按层次遍历）我们把 每层的每个元素 分出来
 *
 *  @param index    按层次遍历树时的位置(从0开始算)
 *  @param rootNode 树根节点
 *
 *  @return 节点
 */
+ (BinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTreeNode *)rootNode {
    //按层次遍历
    if (!rootNode || index < 0) {
        return nil;
    }
    
    NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
    [queueArray addObject:rootNode]; //压入根节点
    while (queueArray.count > 0) {
        
        BinaryTreeNode *node = [queueArray firstObject];
        if (index == 0) {
            return node;
        }
        [queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
        index--; //移除节点，index减少
        
        if (node.leftNode) {
            [queueArray addObject:node.leftNode]; //压入左节点
        }
        if (node.rightNode) {
            [queueArray addObject:node.rightNode]; //压入右节点
        }
    }
    //层次遍历完，仍然没有找到位置，返回nil
    return nil;
}


/**
 *  先序遍历
 *  先访问根，再遍历左子树，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)preTraverSortTree:(BinaryTreeNode *)rootNode
                  handler:(PreSortHandler )handler
{
    if (rootNode) {
        if (handler) {
            handler(rootNode);
        }
        
        // handler is defined by outer side 
        [BinaryTreeNode preTraverSortTree:rootNode.leftNode handler:handler];
        [BinaryTreeNode preTraverSortTree:rootNode.rightNode handler:handler];
        
    }
}

/**
 *  中序遍历
 *  先遍历左子树，再访问根，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */

+(void)midTraverSortTree:(BinaryTreeNode *)rootNode
                 Handler:(MidSortHandler )handler
{
    if(rootNode){
        [BinaryTreeNode midTraverSortTree:rootNode.leftNode Handler:handler];
        if (handler) {
            handler(rootNode);
        }
        [BinaryTreeNode midTraverSortTree:rootNode.rightNode Handler:handler];
    }
}

/**
 *  后序遍历
 *  先遍历左子树，再遍历右子树，再访问根
 *
 *  @param tree 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)postTraverSortTree:(BinaryTreeNode *)tree
                   Handler:(PostSortHandler )handler
{
    if (tree) {
        [BinaryTreeNode postTraverSortTree:tree.leftNode Handler:handler];
        [BinaryTreeNode postTraverSortTree:tree.rightNode Handler:handler];
        
        // tree 一直没变
        if (handler) {
            handler(tree);
        }
    }
}

/**
 *  层次遍历（广度优先） 层次遍历
 按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层，因此又叫广度优先遍历。需要用到队列，在OC里可以用可变数组来实现。
 *
 *  @param tree 二叉树根节点
 *  @param handler  访问节点处理函数
 */
+ (void)levelTraversSortTree:(BinaryTreeNode *)tree
                     Handler:(LevelSortHandler )handler
{
    if (!tree) {
        return;
    }
    
    NSMutableArray *queueArray = [NSMutableArray array];
    [queueArray addObject:tree];
    
    while (queueArray.count>0) {
        
        BinaryTreeNode *node = [queueArray firstObject];
        if (handler) {
            handler(node);
        }
        
        [queueArray removeObjectAtIndex:0];  // 弹出最前面的节点，先进先出原则
        if (node.leftNode) {
            [queueArray addObject:node.leftNode]; // 压入左节点
        }
        
        if (node.rightNode) {
            [queueArray addObject:node.rightNode];  // 压入右节点
        }
    }

}

/*
 二叉树的深度
 二叉树的深度定义为：从根节点到叶子结点依次经过的结点形成树的一条路径,最长路径的长度为树的深度。
 1）如果根节点为空，则深度为0；
 2）如果左右节点都是空，则深度为1；
 3）递归思想：二叉树的深度=max（左子树的深度，右子树的深度）+ 1
 */
/**
 *  二叉树的深度
 *
 *  @param rootNode 二叉树根节点
 *
 *  @return 二叉树的深度
 */
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode
{
    if (!rootNode) {
        return 0;
    }
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return 1;
    }
    
    //左子树深度
    NSInteger leftDepth = [BinaryTreeNode depthOfTree:rootNode.leftNode];
//    NSLog(@"depth is %ld",leftDepth);
    //右子树深度
    NSInteger rightDepth = [BinaryTreeNode depthOfTree:rootNode.rightNode];
    
    // 每一层 的话 +1 个这句话是 层数的累加的关键
//    NSLog(@"hei is %ld",rightDepth);
    return MAX(leftDepth, rightDepth) + 1;
}


/**
 *  二叉树的宽度 二叉树的宽度定义为各层节点数的最大值。  注意是 每层节点数量的最大值
 *  首先 我们分层 然后 求出每一层 的最大值 然后 我们 比较每一层的 最大值
 *  @param tree 二叉树根节点
 *
 *  @return 二叉树宽度
 */
+ (NSInteger )widthOfTree:(BinaryTreeNode *)tree
{
    if (!tree) {
        return 0;
    }
    
    NSMutableArray *queueArray = [NSMutableArray array];
    NSInteger maxWidth = 1;  // at least one node so 
    NSInteger curLevelWidth = 0;
    [queueArray addObject:tree];
    
    while (queueArray.count>0) {
        // 每一层
        curLevelWidth = queueArray.count;
        for (int i=0; i<curLevelWidth; i++)
        {
            
            BinaryTreeNode *node = [queueArray firstObject];
            [queueArray removeObjectAtIndex:0];  // 先入先出 一次只弹出一个 因为我们一次 只加入了一个node的子节点
            
            if (node.leftNode) {
                [queueArray addObject:node.leftNode];
            }
            
            if (node.rightNode) {
                [queueArray addObject:node.rightNode];
            }
        }
        
        maxWidth = MAX(curLevelWidth, maxWidth);
    }
    
    return maxWidth;
}


// 递归思想：二叉树所有节点数=左子树节点数+右子树节点数+1 这是很有意思的一个地方
/**
 *  二叉树的所有节点数
 *
 *  @param rootNode 根节点
 *
 *  @return 所有节点数
 */
+ (NSInteger)numberOfNodesInTree:(BinaryTreeNode *)rootNode
{
    if (!rootNode) {
        return 0;
    }
    
    return  [self numberOfNodesInTree:rootNode.leftNode] + [self numberOfNodesInTree:rootNode.rightNode] + 1;
}

// 二叉树第k层节点数=左子树第k-1层节点数+右子树第k-1层节点数  可能有子树 也可能没有子树
/**
 *  二叉树某层中的节点数
 *
 *  @param level    层 从 第一层开始
 *  @param rootNode 根节点
 *
 *  @return 层中的节点数
 */
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(BinaryTreeNode *)rootNode
{
    //
    if (!rootNode || level<1) {  //  level
        return 0;
    }
    
    if (level == 1) {
        return 1;
    }
    
    return [BinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] + [BinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];
    
}

/**
 *  二叉树叶子节点数  叶子节点，又叫终端节点，是左右子树都是空的节点。 很明显 叶子结点数量 = 左子树叶子结点数量
 *  加上 右子树叶子结点数量
 *
 *  @param rootNode 根节点
 *
 *  @return 叶子节点数
 */
+ (NSInteger)numberOfLeafsInTree:(BinaryTreeNode *)rootNode
{
    if(!rootNode){
        return 0;
    }
    
    // left tree and right tree  also zero
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return  1;
    }
    // return left right numbers total
    return [BinaryTreeNode numberOfLeafsInTree:rootNode.leftNode] + [BinaryTreeNode numberOfLeafsInTree:rootNode.rightNode];
    
}

/*
 二叉树最大距离（二叉树的直径）
 二叉树中任意两个节点都有且仅有一条路径，这个路径的长度叫这两个节点的距离。二叉树中所有节点之间的距离的最大值就是二叉树的直径。
 
 有一种解法，把这个最大距离划分了3种情况：
 
 1）这2个节点分别在根节点的左子树和右子树上，他们之间的路径肯定经过根节点，而且他们肯定是根节点左右子树上最远的叶子节点（他们到根节点的距离=左右子树的深度）。
 
 2）这2个节点都在左子树上
 
 3）这2个节点都在右子树上
 
 综上，只要取这3种情况中的最大值，就是二叉树的直径。
 */
/**
 *  二叉树最大距离（直径）
 *
 *  @param rootNode 根节点
 *
 *  @return 最大距离
 */
+ (NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode
{
    if (!rootNode) {
        return 0;
    }
    
    // //    方案一：（递归次数较多，效率较低）
    NSInteger leftDistance = [BinaryTreeNode maxDistanceOfTree:rootNode.leftNode];
    NSInteger rightDistance = [BinaryTreeNode maxDistanceOfTree:rootNode.rightNode];
    NSInteger distance = [BinaryTreeNode depthOfTree:rootNode.leftNode] + [BinaryTreeNode depthOfTree:rootNode.rightNode];
    
    return  MAX(MAX(leftDistance, rightDistance), distance);
}

// 这个方案效率较低，因为计算子树的深度和最远距离是分开递归的，存在重复递归遍历的情况。其实一次递归，就可以分别计算出深度和最远距离，于是有了第二种方案：但是是整个tree 的递归


/**
 只用一次遍历算出 depth 和 二叉树直径的方法

 @param tree 根节点
 @return return value description
 */
+ (TreeNodeProperty *)nodePropertyOfTree:(BinaryTreeNode *)tree
{
    if (!tree) {
        return nil;
    }
    
    //
    TreeNodeProperty *p = [[TreeNodeProperty alloc]init];

    TreeNodeProperty *leftP = [BinaryTreeNode nodePropertyOfTree:tree.leftNode];
    TreeNodeProperty *righP = [BinaryTreeNode nodePropertyOfTree:tree.rightNode];
    
    p.depth = MAX(leftP.depth, righP.depth) + 1;
    p.distance = MAX(MAX(leftP.distance, righP.distance),(leftP.depth+righP.depth));
    
    return p;
}

/*
 二叉树中某个节点到根节点的路径 计算方法：
 既是寻路问题，又是查找节点问题。
 
 定义一个存放路径的栈（不是队列了，但是还是用可变数组来实现的）
 
 1）压入根节点，再从左子树中查找（递归进行的），如果未找到，再从右子树中查找，如果也未找到，则弹出根节点，再遍历栈中上一个节点。
 
 2）如果找到，则栈中存放的节点就是路径所经过的节点。
 */


/**
 查找某个 节点 到根节点点路径

 @param node 要查找的结点
 @param rootNode 根节点
 @return 路径上的节点
 */
+ (NSArray *)pathOfTreeNode:(BinaryTreeNode *)node
                     InTree:(BinaryTreeNode *)rootNode
{
    NSMutableArray *array = [NSMutableArray array];
    // 放入另外一个func 中进行计算
    [BinaryTreeNode isNode:node inTree:rootNode routePath:array];
    return array;
}


/**
 判断 某个节点 是否在 树tree 中

 @param node 要判断的节点
 @param tree 根节点
 @param routePath 两者之间的路径
 @return YES： 在 tree 中并且返回。相应的rotePath。NO： 没有 并且rotePath 为空。
 */
+(BOOL )isNode:(BinaryTreeNode *)node
        inTree:(BinaryTreeNode *)tree
     routePath:(NSMutableArray *)routePath
{
    if (!node || !tree) {
        return NO;
    }
    
    if (node == tree) {
        [routePath addObject:tree];
        return YES;
    }
    
    // 押入根节点
    BOOL isFind = NO;
    [routePath addObject:tree];
    
    // 先遍历左边树 再查找右边的树
    isFind = [BinaryTreeNode isNode:node inTree:tree.leftNode routePath:routePath];
    if (isFind == NO) {
        isFind = [BinaryTreeNode isNode:node inTree:tree.rightNode routePath:routePath];
    }
    
    if (isFind == NO) {
        [routePath removeLastObject];
    }

    return isFind;
}

/*
     二叉树中两个节点最近的公共父节点
     首先需要明白，根节点肯定是二叉树中任意两个节点的公共父节点（不一定是最近的），因此二叉树中2个节点的最近公共父节点一定在从根节点到这个节点的路径上。因此我们可以先分别找到从根节点到这2个节点的路径，再从这两个路径中找到最近的公共父节点。
 */
/**
 *  二叉树中两个节点最近的公共父节点
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 最近的公共父节点
 */
+ (BinaryTreeNode *)parentOfNode:(BinaryTreeNode *)nodeA andNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode
{
    if (!nodeA || !nodeB || !rootNode) {
        return nil;
    }
    
    NSArray *aPath = [BinaryTreeNode pathOfTreeNode:nodeA InTree:rootNode];
    NSArray *bPath = [BinaryTreeNode pathOfTreeNode:nodeB InTree:rootNode];
    
    NSInteger  aCount = aPath.count;
    NSInteger  bCount = bPath.count;
    // 没有公共节点
    if (aCount <1 || bCount <1) {
        return nil;
    }
    
    // 注意是从 根节点开始的
    for (NSInteger  i = aCount -1; i>=0; i--) {
        for (NSInteger j = bCount -1; j>=0; j--) {
            if ([aPath objectAtIndex:i] == [bPath objectAtIndex:j])
            {
                return [aPath objectAtIndex:i];
            }
        }
    }
    
    
    
    return nil;
}


/**
 *  二叉树中两个节点之间的路径 从查找最近公共父节点衍生出来的。
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 两个节点间的路径
 */
+ (NSArray *)pathFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode
{
    // 首先找出二者的最近父节点
    if (!rootNode || !nodeA || !nodeB) {
        return nil;
    }
    NSMutableArray *path = [NSMutableArray array];
    if (nodeA == nodeB) {
        [path addObject:nodeA];
        [path addObject:nodeB];
        return path;
    }
    //从根节点到节点A的路径
    NSArray *pathA = [self pathOfTreeNode:nodeA InTree:rootNode];
    //从根节点到节点B的路径
    NSArray *pathB = [self pathOfTreeNode:nodeB InTree:rootNode];
    //其中一个节点不在树中，则没有路径
    if (pathA.count == 0 || pathB == 0) {
        return nil;
    }
    //从后往前推，查找第一个出现的公共节点
    for (NSInteger i = pathA.count-1; i>=0; i--) {
        [path addObject:[pathA objectAtIndex:i]];
        for (NSInteger j = pathB.count - 1; j>=0; j--) {
            //找到公共父节点，则将pathB中后面的节点压入path
            if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
                j++; //j++是为了避开公共父节点
                while (j<pathB.count) {
                    [path addObject:[pathB objectAtIndex:j]];
                    j++;
                }
                
                return path;
            }
        }
    }
    return nil;
}

/**
 *  二叉树两个节点之间的距离 可以从两个节点之间的路径衍生出来。
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 两个节点间的距离（-1：表示没有找到路径）
 */
+ (NSInteger)distanceFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {
    if (!rootNode || !nodeA || !nodeB) {
        return -1;
    }
    if (nodeA == nodeB) {
        return 0;
    }
    //从根节点到节点A的路径
    NSArray *pathA = [self pathOfTreeNode:nodeA InTree:rootNode];
    //从根节点到节点B的路径
    NSArray *pathB = [self pathOfTreeNode:nodeB InTree:rootNode];
    
    //其中一个节点不在树中，则没有路径
    if (pathA.count == 0 || pathB == 0) {
        return -1;
    }
    //从后往前推，查找第一个出现的公共节点
    for (NSInteger i = pathA.count-1; i>=0; i--) {
        for (NSInteger j = pathB.count - 1; j>=0; j--) {
            //找到公共父节点
            if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
                //距离=路径节点数-1 （这里要-2，因为公共父节点重复了一次）
                return (pathA.count - i) + (pathB.count - j) - 2;
            }
        }
    }
    return -1;
}

/*
 翻转二叉树
 你会翻转二叉树吗？如果不会，那对不起，我们不会录用你！
 翻转二叉树，又叫求二叉树的镜像，就是把二叉树的左右子树对调（当然是递归的）
 */
/**
 *  翻转二叉树（又叫：二叉树的镜像）  两个左右子树先反转。然后再反转子树
 *
 *  @param rootNode 根节点
 *
 *  @return 翻转后的树根节点（其实就是原二叉树的根节点）
 */
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode
{
    if (!rootNode) {
        return nil;
    }
    
    if (!rootNode.leftNode || !rootNode.rightNode) {
        return rootNode;
    }
    
    [BinaryTreeNode invertBinaryTree:rootNode.leftNode];
    [BinaryTreeNode invertBinaryTree:rootNode.rightNode];

    // this location does not really matter  
    BinaryTreeNode *tmpNode = rootNode.leftNode;
    rootNode.leftNode = rootNode.rightNode;
    rootNode.rightNode = tmpNode;

    
    return rootNode;
}

/*
 判断二叉树是否满二叉树
 满二叉树定义为：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
 满二叉树的一个特性是：叶子数=2^(深度-1)，因此我们可以根据这个特性来判断二叉树是否是满二叉树。
 */
/**
 *  是否满二叉树
 *  满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
 *
 *  @param rootNode 根节点
 *
 *  @return YES：满二叉树，NO：非满二叉树
 */
+ (BOOL)isFullBinaryTree:(BinaryTreeNode *)rootNode
{
    if (!rootNode) {
        return NO;
    }
    
    NSInteger leafNum = [BinaryTreeNode numberOfLeafsInTree:rootNode];
    NSInteger level = [BinaryTreeNode depthOfTree:rootNode];
    
    if (leafNum == pow(2, (level-1))) {
        return YES;
    }
    
    return NO;
}


/*
 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
 */

/*
 判断二叉树是否完全二叉树
 完全二叉树定义为：如果二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布。
 
 完全二叉树必须满足2个条件：
 
 1）如果某个节点的右子树不为空，则它的左子树必须不为空
 
 2）如果某个节点的右子树为空，则排在它后面的节点必须没有孩子节点
 
 这里还需要理解“排在它后面的节点”，回头看看层次遍历算法，我们就能知道在层次遍历时，是从上到下从左到右遍历的，先将根节点弹出队列，再压入孩子节点，因此“排在它后面的节点”有2种情况：
 
 1）同层次的后面的节点
 
 2）同层次的前面的节点的孩子节点（因为遍历前面的节点时，会弹出节点，同时将孩子节点压入队列）
 
 通过上面的分析，我们可以设置一个标志位flag，当子树满足完全二叉树时，设置flag=YES。当flag=YES而节点又破坏了完全二叉树的条件，那么它就不是完全二叉树。
 */


/**
 *  是否完全二叉树    我们一个一个节点 验证
 *  完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布
 *
 *  @param rootNode 根节点
 *
 *  @return YES：是完全二叉树，NO：不是完全二叉树
 */
+ (BOOL)isCompleteBinaryTree:(BinaryTreeNode *)rootNode
{
    if (!rootNode) {  //  根节点为nil 那么 不是
        return NO;
    }
    
    if (!rootNode.leftNode&&!rootNode.rightNode)  // 根节点。 左右节点都为空 那么是完全 二叉树
    {
        return YES;
    }
    
    if (!rootNode.leftNode && rootNode.rightNode) {  // 根节点 右节点
        return NO;
    }
    
    NSMutableArray *queue = [NSMutableArray array];
    [queue addObject:rootNode];
    BOOL isFinalLevel = NO;  // 初始值
    
    while (queue.count>0) {
        //
        BinaryTreeNode *node = [queue firstObject];
        [queue removeObjectAtIndex:0];
        
        // 只留下 左边不为空。或者 左右两边都为空的 情况
        if (!node.leftNode && node.rightNode) {
            return NO;
        }
        
        // 也就是 前面都是 满的二叉树。
        if (isFinalLevel && (node.leftNode || node.rightNode)) {
            return NO;
        }
        
        if (!node.rightNode) {  // 如果 右边出现了空的情况 那么 这是最后一层。
            isFinalLevel = YES;
        }
        
        // 压入新的节点
        if (node.leftNode) {
            [queue addObject:node.leftNode];
        }
        
        if (node.rightNode) {
            [queue addObject:node.rightNode];
        }
        
        

    }
    
    return isFinalLevel;
}


/**
 创建一个 满的二叉树
 
 @return 返回一个 随机的满的二叉树
 */
+ (BinaryTreeNode *)createFullNode
{
    BinaryTreeNode *fourNode = [BinaryTreeNode nodeWithValue:4];
    BinaryTreeNode *fiveNode = [BinaryTreeNode nodeWithValue:5];
    BinaryTreeNode *sixNode = [BinaryTreeNode nodeWithValue:6];
    BinaryTreeNode *sevenNode = [BinaryTreeNode nodeWithValue:7];
    BinaryTreeNode *secondNode = [BinaryTreeNode nodeWithValue:2];
    BinaryTreeNode *threeNode = [BinaryTreeNode nodeWithValue:3];
    BinaryTreeNode *oneNode = [BinaryTreeNode nodeWithValue:1];
    
    secondNode.leftNode = fourNode;
    secondNode.rightNode = fiveNode;
    
    threeNode.leftNode = sixNode;
    threeNode.rightNode = sevenNode;
    
    oneNode.leftNode = secondNode;
    oneNode.rightNode = threeNode;
    
    return oneNode;
}



/**
 创建一个 完全二叉树
 
 @return return value description
 */
+ (BinaryTreeNode *)createCompleteNode
{
    BinaryTreeNode *fourNode = [BinaryTreeNode nodeWithValue:4];
    BinaryTreeNode *fiveNode = [BinaryTreeNode nodeWithValue:5];
    BinaryTreeNode *sixNode = [BinaryTreeNode nodeWithValue:6];
//    BinaryTreeNode *sevenNode = [BinaryTreeNode nodeWithValue:7];
    BinaryTreeNode *secondNode = [BinaryTreeNode nodeWithValue:2];
    BinaryTreeNode *threeNode = [BinaryTreeNode nodeWithValue:3];
    BinaryTreeNode *oneNode = [BinaryTreeNode nodeWithValue:1];
    
    secondNode.leftNode = fourNode;
    secondNode.rightNode = fiveNode;
    
    threeNode.leftNode = sixNode;
//    threeNode.rightNode = sevenNode;  // 第七个节点 没有连上
    
    oneNode.leftNode = secondNode;
    oneNode.rightNode = threeNode;
    
    return oneNode;
}


+ (BinaryTreeNode *)nodeWithValue:(NSInteger)value
{
    BinaryTreeNode *node = [BinaryTreeNode new];
    node.value = value;
    return node;
}

/*
 判断二叉树是否平衡二叉树
 平衡二叉树定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树又叫AVL树。
 */

/**
 *  是否平衡二叉树
 *  平衡二叉树：即AVL树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
 *
 *  @param rootNode 根节点
 *
 *  @return YES：平衡二叉树，NO：非平衡二叉树
 */
+ (BOOL)isAVLBinaryTree:(BinaryTreeNode *)rootNode
{
    if (!rootNode) {
        return NO;
    }
    
    //
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return YES;
    }
    
    NSInteger leftDepth = [BinaryTreeNode depthOfTree:rootNode.leftNode];
    NSInteger rightDepth = [BinaryTreeNode depthOfTree:rootNode.rightNode];
    
    if (ABS(leftDepth-rightDepth)<=1) {
        return YES;
    }
    
    return NO;
    
}

























@end
